Letter Combinations of a Phone Number

发表于 | 分类于

[Leetcode]Letter Combinations of a Phone Number

Given a digit string, return all possible letter combinations that the number could represent.
A mapping of digit to letters (just like on the telephone buttons) is given below.
phonenum

1
2
Input:Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

Note:
Although the above answer is in lexicographical order, your answer could be in any order you want.

解题思路：
使用backtracking，从后往前将所有的手机号码对应的字母返回给前一个号码，将其组合获得结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
kvmaps = {'1': '*',
          '2': 'abc',
          '3': 'def',
          '4': 'ghi',
          '5': 'jkl',
          '6': 'mno',
          '7': 'pqrs',
          '8': 'tuv',
          '9': 'wxyz',
          '0': ' '
          }
class Solution(object):
    
    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        if digits == "":
            return []
        combinations = []
        if len(digits) == 1:
            for x in kvmaps[digits[0]]:
                combinations.append(x)
        else:
            for c in self.letterCombinations(digits[1:]):
                for x in kvmaps[digits[0]]:
                    combinations.append(x + c)
        return combinations